package primary.primary0;

import java.util.*;

/**
 * 图, 最短路径,
 */
public class S0743网络延迟时间 {
    /**
     * 57, dfs, dijkstra
     * 做点图的题目, 不知道这个有向边该如何存储,
     * 有向边及其路径长按照Map<Integer, List<Integer[]>>来存储吧
     * 用一个一维数组存储这个最短路径, 然后层序遍历, 同时兼职visited的功能
     * 这个层序遍历, 需要用个什么东西来一边存一边取
     */
    public static int networkDelayTime(int[][] times, int n, int k) {
        // 第一个Integer是起始节点, 后一个Integer[] 是边的终点及其长度, 一个起点可能有多个终点
        Map<Integer, List<Integer[]>> graph = new HashMap<>();
        for(int i = 0; i < n + 1; i++)
            graph.put(i, new LinkedList<>());
        for(int[] edge : times){
            // 只记录有出度的点, 看起来没问题, 实际上一些只入不出的节点也是会需要访问并返回一个空List的。
//            if(!graph.containsKey(edge[0])){
//                graph.put(edge[0], new LinkedList<>());
//            }
            graph.get(edge[0]).add(new Integer[]{edge[1], edge[2]});
        }
        Integer[] record = new Integer[n + 1]; // 序号从1开始, 前面加个不参加计算的0位
        record[0] = -1;
        Arrays.fill(record, Integer.MAX_VALUE);

        // 这里用一个deque, 不算是边遍历边修改, 因为所有操作都不在遍历之中。集合的边遍历边修改很麻烦。
        Deque<Integer> dfsRecord = new LinkedList<>();
        dfsRecord.addLast(k);
        record[k] = 0;
        // 典型的dijkstra, 层序遍历, 然后在遍历的过程中更新最小路径,
        // 这种解法只能找到一个点到其他点的最小路程值, 不知道怎么获取路径
        while(!dfsRecord.isEmpty()){
            Integer curNode = dfsRecord.pollFirst();
            List<Integer[]> curNodeAimList = graph.get(curNode);
            for(Integer[] curNodeAimListEle : curNodeAimList){
                if(record[curNode] + curNodeAimListEle[1] < record[curNodeAimListEle[0]]){
                    // 如果对于某一个节点产生了新的最小路径, 那么将需要对这个节点可达的点进行一个更新
                    // 这种更新通过把它塞到遍历的deque里面让他再一次被dfs访问来实现。
                    record[curNodeAimListEle[0]] = record[curNode] + curNodeAimListEle[1];
                    dfsRecord.addLast(curNodeAimListEle[0]);
                }
            }
        }
        int maxTime = -1;
        for(Integer i: record){
            maxTime = Math.max(i, maxTime);
        }
        // 这里如果有不可达的节点, 需要返回-1, 但是不可达在这里是Integer.MAX_VALUE, 其实应该使用负数来着。
        return maxTime == Integer.MAX_VALUE? -1: maxTime;
    }

    /**
     * 用优先队列, 堆, 给dijkstra进行一点优化, 即运算过程中的距离数组中, 最小的那一个节点时肯定不会再变小了,
     * 我们每次运算都可以确定其中一个节点的位置, 因为他需要最大的那个节点, 所以最后确认的那个节点就是最大的。
     */
    public static int networkDelayTime2(int[][] times, int n, int k) {
        // 第一个Integer是起始节点, 后一个Integer[] 是边的终点及其长度, 一个起点可能有多个终点
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for(int i = 0; i < n + 1; i++)
            graph.put(i, new LinkedList<>());
        for(int[] edge : times){
            graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
        }
        Integer[] record = new Integer[n + 1]; // 序号从1开始, 前面加个不参加计算的0位
        record[0] = -1;
        Arrays.fill(record, Integer.MAX_VALUE);

        // 这里用了一个小顶堆, 每次拿最上面那一个点就行, 注意堆是会有重复值的, 多次添加会被多次消费
        // 这里优先队列有点不一样, 在添加节点的时候, 比较规则依赖的record是会变化的
        // todo: 但是我们拿出一个点, 队列重排, 产生新的规则之后, 重排的结果还是顶堆是最小的吗?
        Queue<Integer> dfsRecord = new PriorityQueue<>((a, b)->{return record[a] - record[b];});
        dfsRecord.add(k);
        record[k] = 0;

        // 这里比上面多了一个visited, 因为while中语句每次执行都会唯一确定最小的那个点的值, 这个值就不会变了
        boolean[] visited = new boolean[n];

        while(!dfsRecord.isEmpty()){
            Integer curNode = dfsRecord.poll();
            if(visited[curNode]) continue;
            visited[curNode] = true;
            List<int[]> curNodeAimList = graph.get(curNode);
            for(int[] curNodeAimListEle : curNodeAimList){
                // 这里修改了record, 那么下一次获取的curNode还是最小的那一个吗?
                record[curNodeAimListEle[0]] = Math.min(record[curNodeAimListEle[0]], record[curNode] + curNodeAimListEle[1]);
                dfsRecord.add(curNodeAimListEle[0]);
            }
        }
        int maxTime = -1;
        for(Integer i: record){
            maxTime = Math.max(i, maxTime);
        }
        // 这里如果有不可达的节点, 需要返回-1, 但是不可达在这里是Integer.MAX_VALUE, 其实应该使用负数来着。
        return maxTime == Integer.MAX_VALUE? -1: maxTime;
    }

    public static void main(String[] args) {
        //[[2,1,1],[2,3,1],[3,4,1]]
        //int[][] times = new int[][]{new int[]{2, 1, 1}, new int[]{2, 3, 1}, new int[]{3, 4, 1}};
        int[][] times = new int[][]{new int[]{1, 2, 1}};
        System.out.println(networkDelayTime(times, 2,  2));
    }
}
